public class test03 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
        public List<Integer> inorderTraversal(TreeNode root) {
            //迭代法
            //先一直往左，找到最左
            Deque<TreeNode> stack = new LinkedList<>();
            List<Integer> res = new ArrayList<>();
            if(root==null){
                return res;
            }
            TreeNode cur = root;
            while(!stack.isEmpty() || cur!=null){
                if(cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }else{
                    //到最左了
                    cur = stack.pop();
                    res.add(cur.val);
                    cur = cur.right;
                }
            }
            return res;
        }
}
